﻿using System.Text;

namespace ExpressionCompute
{

    /// <summary>
    /// 编写代码，计算用户输入的四则运算表达式
    /// 转换中缀表达式为逆波兰表达式。
    /// 计算逆波兰表达式的值。
    /// </summary>
    public class Program
    {
        static void Main(string[] args)
        {
            try
            {
                //获得用户输入
                var inputString = GetInput();
                Console.WriteLine($"Result={Compute(inputString)}");
            }
            catch (Exception ex)
            {
                Console.WriteLine(ex.Message);
            }
            finally
            {
                Console.WriteLine("程序结束");
            }
        }

        /// <summary>
        /// 计算过程
        /// </summary>
        /// <param name="input"></param>
        /// <returns></returns>
        public static double Compute(string input)
        {
            var resultList = InputProcess(input);
            var resultQueue = RPNConvert(resultList.ToList());
            var result = ComputeRPN(resultQueue);
            return result;
        }

        /// <summary>
        /// 获得用户输入
        /// </summary>
        /// <returns></returns>
        static string GetInput()
        {
            Console.Clear();
            Console.Write("请输入表达式");
            var inputString = Console.ReadLine();
            if (string.IsNullOrEmpty(inputString)) throw new Exception("用户输入有误");
            return inputString;
        }

        /// <summary>
        /// 输入处理，检查非法元素
        /// </summary>
        /// <param name="input"></param>
        /// <returns>List Of number & operators</returns>
        static IEnumerable<string> InputProcess(string input)
        {
            //所有合法字符
            char[] validChars = { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', '.', '+', '-', '*', '/', ' ', '(', ')' };

            List<string> result = new List<string>();

            int i = 0;
            var chars = input.ToCharArray();
            while (i < chars.Length)
            {


                char ch = chars[i];
                if (!validChars.Contains(ch)) throw new Exception($"非法字符\"{ch}\"");

                if (IsDigit(ch))
                {
                    StringBuilder sb = new StringBuilder();
                    while (IsDigit(ch))
                    {
                        sb.Append(ch);
                        i++;
                        if (i == chars.Length) break;
                        ch = chars[i];
                    }
                    result.Add(sb.ToString());
                    i--;
                }
                else if (IsOperator(ch))
                    result.Add(ch.ToString());
                else if ("()".Contains(ch))
                    result.Add(ch.ToString());
                i++;
            }
            return result;
        }

        /// <summary>
        /// 判断是否数字
        /// </summary>
        /// <param name="ch"></param>
        /// <returns></returns>
        static bool IsDigit(char ch)
        {
            if (ch >= '0' && ch <= '9' || ch == '.') return true;
            return false;
        }

        /// <summary>
        /// 判断是否数字
        /// </summary>
        /// <param name="ch"></param>
        /// <returns></returns>
        static bool IsDigit(string str)
        {
            char ch = str.ToArray()[0];
            return IsDigit(ch);
        }

        /// <summary>
        /// 判断是否操作符
        /// </summary>
        /// <param name="ch"></param>
        /// <returns></returns>
        static bool IsOperator(char ch)
        {
            if (ch == '+' || ch == '-' || ch == '*' || ch == '/') return true;
            return false;
        }

        /// <summary>
        /// 判断是否操作符
        /// </summary>
        /// <param name="ch"></param>
        /// <returns></returns>
        static bool IsOperator(string str)
        {
            char ch = str.ToArray()[0];
            return IsOperator(ch);
        }

        /// <summary>
        /// 运算符优先级
        /// </summary>
        /// <param name="op"></param>
        /// <returns></returns>
        static int Precedence(string op)
        {
            switch (op)
            {
                case "+":
                case "-":
                    return 3;
                case "*":
                case "/":
                    return 5;
                default:
                    return 6; // 默认高优先级
            }
        }

        /// <summary>
        /// 逆波兰表达式
        /// </summary>
        /// <returns></returns>
        static Queue<string> RPNConvert(List<string> input)
        {
            /*
                初始化：
                创建一个空的输出队列。
                创建一个空的操作符栈。
                读取中缀表达式：
                从左到右逐个读取中缀表达式中的每个符号（包括操作数和操作符）。
                处理每个符号：
                -如果读取到的是操作数（数字或变量），直接将其添加到输出队列。
                -如果读取到的是左括号 (，将其压入操作符栈。
                -如果读取到的是右括号 )，弹出操作符栈中的操作符并将其添加到输出队列，直到遇到左括号 (。然后丢弃这对括号。
                -如果读取到的是操作符（如 +, -, *, /）：
                -当栈顶的操作符优先级大于或等于当前操作符时，从栈中弹出这些操作符并添加到输出队列。
                -将当前操作符压入栈。
                -如果读取到的是结束符（表示表达式结束），将操作符栈中的所有操作符依次弹出并添加到输出队列。
                -输出逆波兰表达式：
                -当所有的符号都处理完毕后，输出队列中的内容就是逆波兰表达式。
             */
            //操作符栈
            var opStack = new Stack<string>();
            var result = new Queue<string>();
            foreach (var item in input)
            {
                if (IsDigit(item)) result.Enqueue(item);
                else if (item == "(") opStack.Push(item);
                else if (item == ")")
                {
                    var op = "";
                    do
                    {
                        op = opStack.Pop();
                        if (op != "(") result.Enqueue(op);
                    } while (op != "(");
                }
                else if (IsOperator(item))
                {
                    while (opStack.Count > 0 && opStack.Peek() != "(" && Precedence(opStack.Peek()) >= Precedence(item))
                    {
                        result.Enqueue(opStack.Pop());
                    }
                    opStack.Push(item);
                }
            }
            while (opStack.Any())
            {
                result.Enqueue((string)opStack.Pop());
            };
            return result;
        }

        /// <summary>
        /// 计算逆波兰表达式
        /// </summary>
        /// <param name="input"></param>
        /// <returns></returns>
        static double ComputeRPN(Queue<string> input)
        {
            /*
                初始化一个栈。
                从左到右扫描逆波兰表达式中的每个元素。
                如果元素是操作数，将其压入栈。
                如果元素是运算符，从栈中弹出所需数量的操作数，执行相应的运算，然后将结果压回栈。
                最终，栈顶的元素就是表达式的计算结果。 
             */
            Stack<double> opStack = new Stack<double>();

            while (input.Any())
            {
                var item = input.Dequeue();
                if (IsDigit(item)) opStack.Push(double.Parse(item));
                else
                {
                    var number1 = opStack.Pop();
                    var number2 = opStack.Pop();
                    switch (item)
                    {
                        case "+":
                            opStack.Push((number1 + number2));
                            break;
                        case "-":
                            opStack.Push((number2 - number1));
                            break;
                        case "*":
                            opStack.Push((number1 * number2));
                            break;
                        case "/":
                            opStack.Push((number2 / number1));
                            break;

                    }
                }
            }
            return opStack.Pop();
        }
    }
}

